// https://blog.csdn.net/rxbook/article/details/130846053
package main

import "fmt"

func test1() {
	// O(1) 常量级别复杂度
	var a = 5
	var b = 3
	var c = 1
	fmt.Println(a + b + c)

	// O(logn) 和 O(n * logn) 对数级别
	var d = 1
	for d <= 10 {
		// 变量d的值从1开始取，每循环一次就乘以2;当大于10时循环结束，变量d的取值是一个等比数列。
		// 所以这段代码的时间复杂度是 O(log2n),注意这个2是下标2,输入法打不出来.
		d = d * 2
	}
	fmt.Println(d)

	// O(m+n) ：这种情况的复杂度由m和n两个数据的规模来决定
	fmt.Println(test2(100, 300))
}

func test2(m, n int) int {
	// 无法事先评估 m 和 n 谁的量级大，所以不能利用加法法则省略掉其中一个;
	// 所以这段代码的时间复杂度就是 O(m+n)
	var sum1 = 0
	for i := 1; i < m; i++ {
		sum1 = sum1 + i
	}

	var sum2 = 0
	for j := 1; j < n; j++ {
		sum2 = sum2 + j
	}

	return sum1 + sum2
}

// 逆序输出数组的元素,方法1:逐个遍历并逆序赋值
// 时间复杂度是O(n),空间复杂度是O(n)
func reverseArray1(arr [5]int) [5]int {
	var newArr = [5]int{}
	for i := 0; i < len(arr); i++ {
		newArr[len(arr)-i-1] = arr[i]
	}
	return newArr
}

// 逆序输出数组的元素,方法2:前后互相调换
// 时间复杂度是O(n/2),也就是O(n),空间复杂度是O(1)
func reverseArray2(arr [5]int) [5]int {
	var tmp = 0
	for i := 0; i < len(arr)/2; i++ {
		tmp = arr[i]
		arr[i] = arr[len(arr)-i-1]
		arr[len(arr)-i-1] = tmp
	}
	return arr
}

// 力扣 https://leetcode.cn/problems/two-sum/
// 两数之和,方法1:暴力解法，双重循环遍历，时间复杂度: O(n^2)，空间复杂度: O(1)
func twoSum1(nums []int, target int) []int {
	// 第一轮遍历
	for i := 0; i < len(nums); i++ {
		// 第二轮遍历不能重复计算了
		for j := i + 1; j < len(nums); j++ {
			if nums[i]+nums[j] == target {
				// 注意 leetcode 中要求返回的是索引位置
				return []int{i, j}
			}
		}
	}
	return []int{}
}

// 两数之和,方法2:空间换时间，使用map（键值对）存储。时间复杂度: O(n)，空间复杂度: O(n)
func twoSum2(nums []int, target int) []int {
	find := map[int]int{}
	for j, num := range nums {
		if i, ok := find[target-num]; ok {
			return []int{i, j}
		}
		// 每一轮都存下当前num和对应的index到map中
		find[num] = j
	}
	return []int{}
}

func main() {
	test1()
	fmt.Println(reverseArray1([5]int{1, 2, 3, 4, 5})) //[5 4 3 2 1]
	fmt.Println(reverseArray2([5]int{1, 2, 3, 4, 5})) //[5 4 3 2 1]

	fmt.Println(twoSum1([]int{2, 7, 11, 15}, 22)) //[1 3]
	fmt.Println(twoSum2([]int{2, 7, 11, 15}, 22)) //[1 3]
}
